Technical Field
Nodes in a computer network can also function as encoders. In particular, a node operating as encoder does not just forward (i.e. relay or replicate) information received from an input link, it also encodes such information. Coding at a node in a network is known as network coding.
Networks can be modeled as graphs with unit capacity directed links, one or more discrete sources, and one or more receivers, as shown in R. Koetter and M. Medard, “An algebraic approach to network coding,” IEEE/ACM Transactions on Networking, Vol 11 Issue 5, October 2003, incorporated herein by reference in its entirety. A common communication problem on networks is the multicast connection problem, where all source processes have to be transmitted to each of the receiver nodes.
Description of Related Art
Network coding enables connections that are not possible if limited to forwarding. In particular, it has been shown in R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network Information Flow”, IEEE Transactions on Information Theory and vol. 46, pp. 1204-1216 (2000), incorporated herein by reference in its entirety, that it is, in general, not optimal to simply route or replicate the information to be multicast. Rather, by employing coding at the nodes, bandwidth can generally be saved.
A network can be represented as a directed graph, as shown in R. Koetter and M. Medard, “Beyond Routing: An Algebraic Approach to Network Coding”, Proceedings of the 2002 IEEE Infocom (2002), incorporated herein by reference in its entirety. The graph comprises source nodes and receiver nodes, where discrete independent random processes (source processes) are observable at one or more of the source nodes and output processes are observable at the receiver nodes. In the above reference, an algorithm for finding a linear coding solution to a given multicast connection problem, using knowledge of the entire network topology, is disclosed.
However, in applications where communication is limited or expensive, it may be preferable to determine each node's behavior in a distributed manner. Determination of node behavior in a distributed manner is based on information available locally at each node and/or minimal control signaling, without requiring centralized coordination or knowledge of the overall network topology.
It has been shown in T. Ho, R. Koetter, M. Medard, D. R. Karger and M. Effros, “The Benefits of Coding over Routing in a Randomized Setting,” International Symposium on Information Theory (ISIT) 2003, incorporated herein by reference in its entirety, that the multicast connection problem can be solved in a distributed manner by means of random linear network coding.
It has been shown in T. Ho, S. Jaggi, S. Vyetrenko and L. Xia, “Universal and Robust Distributed Network Codes,” Infocom 2011, incorporated herein by reference in its entirety, that the multicast connection problem can be solved with zero-error deterministic distributed network codes, but with impractical complexity and large delay.